package linear_list.leetcode.medium;

/**
 * @author Stark
 * @description 回文链表
 * 题目链接：https://leetcode-cn.com/problems/aMhZSa
 * @date 2022/4/11 19:54
 **/
public class Offer027_IsPalindrome {
    static int choice = 2;
    public static boolean isPalindrome(ListNode head) {
        if(choice == 1) {
            //方法1
            //新建一条链表为原链表的逆置后的结果
            //比较两条链表前一半结点值是否相同,相同则是回文链表,反之不是
            //时间复杂度O(n),空间复杂度O(n)
            if(head.next == null)
                return true;
            ListNode pHead = head;
            ListNode head2 = null;
            while (pHead != null) {
                head2 = new ListNode(pHead.val, head2);
                pHead = pHead.next;
            }
            ListNode fast = head;
            while (fast != null && fast.next != null) {
                if (head.val != head2.val)
                    return false;
                head = head.next;
                head2 = head2.next;
                fast = fast.next;
            }
            return true;
        }else if(choice == 2){
            //方法二,先遍历一遍,得到中间结点
            //将中间结点后面的链表逆置
            //从原链表和逆置后的链表逐个进行比较
            //当不同则返回false,反之为true
            //时间复杂度O(n),空间复杂度O(1)
            if(head.next == null)
                return true;
            ListNode middleNode = middleNode(head);
            ListNode head2 = reverseList(middleNode);
            while(head2 != null){
                if(head.val != head2.val){
                    return false;
                }
                head = head.next;
                head2 = head2.next;
            }
            return true;
        }
        return false;
    }

    private static ListNode reverseList(ListNode middleNode) {
        if(middleNode.next == null)
            return middleNode;
        ListNode head = null;
        while(middleNode != null){
            ListNode next = middleNode.next;
            //这里注意不要写成连等式
            middleNode.next = head;
            head = middleNode;
            middleNode = next;
        }
        return head;
    }

    private static ListNode middleNode(ListNode head) {
        ListNode fast = head,slow = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(0,null);
        ListNode node2 = new ListNode(0,node1);
        ListNode node3 = new ListNode(1,node2);
        isPalindrome(node3);
    }
}
